We study the problem of estimating the best B term Fourier representation fora given frequency-sparse signal (i.e., vector) $\textbf{A}$ of length $N \ggB$. More explicitly, we investigate how to deterministically identify B of thelargest magnitude frequencies of $\hat{\textbf{A}}$, and estimate theircoefficients, in polynomial$(B,\log N)$ time. Randomized sub-linear timealgorithms which have a small (controllable) probability of failure for eachprocessed signal exist for solving this problem. However, for failureintolerant applications such as those involving mission-critical hardwaredesigned to process many signals over a long lifetime, deterministic algorithmswith no probability of failure are highly desirable. In this paper we build onthe deterministic Compressed Sensing results of Cormode and Muthukrishnan (CM)\cite{CMDetCS3,CMDetCS1,CMDetCS2} in order to develop the first knowndeterministic sub-linear time sparse Fourier Transform algorithm suitable forfailure intolerant applications. Furthermore, in the process of developing ournew Fourier algorithm, we present a simplified deterministic Compressed Sensingalgorithm which improves on CM's algebraic compressibility results whilesimultaneously maintaining their results concerning exponential decay.
展开▼
机译：我们研究了为给定的频率稀疏信号（即矢量）长度为\ N \ ggB $的频率稀疏信号（即矢量）估计最佳B项傅立叶表示的问题。更明确地讲，我们研究如何确定多项式$（B，\ log N）$时间中最大幅度频率为\\ hat {\ textbf {A}} $的B并估算其系数。存在用于解决每个问题的随机的次线性时间算法，其对于每个处理的信号具有较小的（可控制的）故障概率。但是，对于容错应用程序（如涉及关键任务硬件的应用程序），这些应用程序被设计为可以在很长的使用寿命内处理许多信号，因此非常需要确定性的算法，而该算法不会发生故障。在本文中，我们基于Cormode和Muthukrishnan（CM）\ cite {CMDetCS3，CMDetCS1，CMDetCS2}的确定性压缩感知结果，以开发第一个已知的确定性亚线性时间稀疏傅里叶变换算法，适用于容错应用。此外，在开发新的傅立叶算法的过程中，我们提出了一种简化的确定性压缩感知算法，该算法改进了CM的代数可压缩性结果，同时保持了它们关于指数衰减的结果。
展开▼
